In the absence of control flow instructions, microprocessors fetch instructions sequentially and execute them. That is, the default action is for the microprocessor to fetch an instruction, and then to fetch the next sequential instruction, and then to fetch the next sequential instruction, and so forth. However, control flow instructions instruct the microprocessor to deviate from this sequential fetching regime. Microprocessors include in their instruction set architecture some form of conditional branch instruction that specifies a branch condition state (typically a condition flag or value in a general purpose register) and a branch condition (for example, bit set or bit clear or equal to zero or greater than a constant value). The conditional branch instruction also specifies a branch target address. The microprocessor examines the branch condition state in light of the branch condition to determine whether the branch condition state satisfies the branch condition specified by the conditional branch instruction. If the branch condition state satisfies the branch condition, the microprocessor begins fetching instructions at the branch target address rather than fetching the next sequential instruction.
As is well-known in the art of microprocessors, modern microprocessors include a pipeline of stages, each of which performs a different task with respect to program instructions. In a standard textbook model of a pipelined microprocessor, the stages include instruction fetch, instruction decode, operand fetch, execute, and result write-back stages. Conditional branch instructions within a program may significantly increase the amount of time required by the microprocessor to execute the program. This is because conventionally it is the execute stage that resolves the conditional branch instruction, i.e., that determines whether the branch condition state satisfies the branch condition. One reason for this is because there may be instructions in the program that are older in program order than the conditional branch instruction that update the branch condition state. Thus, the microprocessor must wait until the execution units produce the result of the older instructions, which are the source operands to the conditional branch instruction that constitute the branch condition state, before the operand fetch stage can fetch the source operands for the conditional branch instruction so that it can be issued for execution. However, the microprocessor may have fetched and processed in varying degrees many of the next sequential instructions after the conditional branch instruction and that are newer in program order than the conditional branch instruction by the time the execution units resolve the conditional branch instruction. This is particularly true in deeply pipelined and/or out-of-order execution microprocessors. If the execution units determine that the branch condition state satisfies the branch condition (i.e., the conditional branch instruction will be taken), the microprocessor must flush all the sequentially fetched instructions after the conditional branch instruction and commence fetching at the branch target address instead. This may significantly lengthen the time required by the microprocessor to execute the program.
To solve this problem, modern microprocessors include branch predictors that attempt to predict the direction (i.e., whether the branch condition state will satisfy the branch condition, referred to as “taken”, or not satisfy it, referred to as “not taken”). However, the branch predictors may mispredict the direction, in which case the microprocessor incurs a branch misprediction penalty because it must flush the pipeline of the erroneously fetched instructions and commence fetching at the correct address (i.e., either the next sequential address or the branch target address, depending upon whether the correct direction). Again, this may significantly lengthen program execution time, as discussed above, particularly in the presence of some conditional branch instructions within programs that may be difficult to predict with much accuracy. Consequently, an approach has been taken to attempt to correctly resolve conditional branch instructions early enough in the pipeline to override the branch predictors. Such an approach is described in U.S. Pat. No. 5,805,876 issued to Bose et al., entitled “METHOD AND SYSTEM FOR REDUCING AVERAGE BRANCH RESOLUTION TIME AND EFFECTIVE MISPREDICTION PENALTY IN A PROCESSOR”. However, a disadvantage of the microprocessor described in Bose et al. is that it selectively resolves the conditional branch instructions early. That is, it only resolves conditional branch instructions early if they satisfy a specific set of requirements, such as being in the first dispatchable position within an instruction buffer when first detected.
Therefore, what is needed is a microprocessor with an improved technique for allowing programs to conditionally branch.